""" Rebiks Cube solver """

from S3D import range_2
from collections import deque

#
#             --- Up ---
#            | 10 11 12 |
#            | 13 14 15 |
#            | 16 17 18 |
#  -- Left -- - Front  - - Right  - -- Back --
# | 40 41 42 | 00 01 02 | 50 51 52 | 26 27 28 |
# | 43 44 45 | 03 04 05 | 53 54 55 | 23 24 25 |
# | 46 47 48 | 06 07 08 | 56 57 58 | 20 21 22 |
#  -- --- --  -- Down -- -- ---- -- -- ---- --
#            | 30 31 32 |
#            | 33 34 35 |
#            | 36 37 38 |
#             -- ---- --
import heapq

FACE_FRONT      = 0
FACE_UP         = 1
FACE_BACK       = 2
FACE_DOWN       = 3
FACE_LEFT       = 4
FACE_RIGHT      = 5
FACES_COUNT     = 6

DIR_UP          = 0
DIR_RIGHT       = 1
DIR_DOWN        = 2
DIR_LEFT        = 3

COLORS          = ('W', 'O', 'Y', 'R', 'G', 'B')

FINAL_PERM      = tuple(face for face in range(6) for _ in range(9))

FACE_SIDES = [
    [(0, 0), (1, 0), (2, 0)],
    [(2, 0), (2, 1), (2, 2)],
    [(2, 2), (1, 2), (0, 2)],
    [(0, 2), (0, 1), (0, 0)],
]

def makeIndex(face, x, y):
    return face * 9 + y * 3 + x

class RubikFace:
    __slots__  = ('colors', 'neighbours', 'face')

    def __init__(self, face):
        self.face   = face
        self.colors = [makeIndex(face, y, x) for x, y in range_2(3, 3)]

    def reset(self):
        for x, y in range_2(3, 3):
            self.colors[x + y * 3] = makeIndex(self.face, x, y)

    def setNeighbours(self, up, right, down, left):
        self.neighbours = (up, right, down, left)

    def getColor(self, x, y):
        return self.colors[x + y * 3]

    def setColor(self, x, y, color):
        self.colors[x + y * 3] = color

    def setSide(self, face, values):
        side = self.neighbours.index(face)
        for (x, y), color in zip(FACE_SIDES[side], values):
            self.colors[y * 3 + x] = color

    def getSide(self, face):
        side = self.neighbours.index(face)
        res = []
        for x, y in FACE_SIDES[side]:
            res.append(self.colors[y * 3 + x])
        return res

class RubikCube:
    def __init__(self):
        self.faces = tuple(RubikFace(face) for face in range(FACES_COUNT))

        front, up, back, down, left, right = self.faces

        front.setNeighbours(up,    right, down,  left)
        up.setNeighbours   (back,  right, front, left)
        back.setNeighbours (down,  right, up,    left)
        down.setNeighbours (front, right, back,  left)
        left.setNeighbours (up,    front, down,  back)
        right.setNeighbours(up,    back,  down,  front)

    def rotateFace(self, face, clockwise = True):
        self.print()

        rotMove = (DIR_UP, DIR_RIGHT, DIR_DOWN, DIR_LEFT) if clockwise else (DIR_UP, DIR_LEFT, DIR_DOWN, DIR_RIGHT)

        f = self.faces[face]
        prevVals = [f.neighbours[side].getSide(f) for side in rotMove]

        for index, side in enumerate(rotMove):
            f.neighbours[side].setSide(f, prevVals[(index + 3) % 4])
            #self.print()

        rotMove = [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1)]
        if clockwise:
            rotMove.reverse()

        x0, y0 = rotMove[0]
        first = f.getColor(x0, y0)

        for index, (x, y) in enumerate(rotMove):
            prevIndex = (index + 2) % len(rotMove)
            x1, y1 = rotMove[prevIndex]
            f.setColor(x, y, f.getColor(x1, y1))
            #self.print()

        #x0, y0 = rotMove[-2]
        f.setColor(x0, y0, first)

        self.print()
        self.check()

    def getPermutationAndReset(self):
        perm = []

        for face in range(FACES_COUNT):
            cur = self.faces[face]
            for x, y in range_2(3, 3):
                perm.append(cur.getColor(x, y))
            cur.reset()

        self.check()    

        return perm

    def getRotationList(self):
        res = []

        for face in range(FACES_COUNT):
            self.rotateFace(face)
            res.append(self.getPermutationAndReset())
            self.rotateFace(face, False)
            res.append(self.getPermutationAndReset())

        return res

    def getNeighbourSide(self, face, dir):
        cur  = self.faces[face]
        return cur.neighbours[dir].getSide(cur)

    def print(self):
        # print up face
        print('            ----------')
        f = self.faces[FACE_UP]
        for y in range(3):
            print('           | ', end = '')
            for x in range(3):
                print("%02d " % f.colors[x + y * 3], end = '')
            print('|')

        # print left, front, right, back faces
        print(' ---------- ---------- ---------- ----------')
        for y in range(3):
            print('| ', end = '')
            for face in (FACE_LEFT, FACE_FRONT, FACE_RIGHT, FACE_BACK):
                f = self.faces[face]
                for x in range(3):
                    print("%02d " % f.colors[x + y * 3], end = '')
                print('| ', end = '')
            print('')

        # print down face
        print(' ---------- ---------- ---------- ----------')
        f = self.faces[FACE_DOWN]
        for y in range(3):
            print('           | ', end = '')
            for x in range(3):
                print("%02d " % f.colors[x + y * 3], end = '')
            print('|')
        print('            ----------')

    def check(self):
        mark = [False for _ in range(9 * FACES_COUNT)]

        for face in range(FACES_COUNT):
            f = self.faces[face]
            for index in range(9):
                mark[f.colors[index]] = True

        assert all(mark)

CUBE = RubikCube()
ROTATIONS = CUBE.getRotationList()
    
class RubikState:
    __slots__ = ('state', 'back', 'weight')

    def __init__(self, state, back):
        assert isinstance(state, tuple)
        assert len(state) == 3 * 3 * 6
        self.state  = state
        self.back   = back

        self.weight = 0

        def check(index):
            return state[index] == FINAL_PERM[index]

        for face in range(6):
            for x, y in range_2(3, 3):
                index = makeIndex(face, x, y)
                if not check(index):
                    continue

                self.weight += 5 if x == 1 or y == 1 else 1

                # left-right
                if x == 0 or x == 2:
                    a, b, c = CUBE.getNeighbourSide(face, DIR_LEFT if x == 0 else DIR_RIGHT)
                    if y == 0 and check(c) or y == 2 and check(a):
                        self.weight += 100
                        pass
                    elif y == 1 and check(b):
                        self.weight += 1000

                # up-down
                if y == 0 or y == 2:
                    a, b, c = CUBE.getNeighbourSide(face, DIR_UP if y == 0 else DIR_DOWN)
                    if x == 0 and check(c) or x == 2 and check(a):
                        self.weight += 100
                        pass
                    elif x == 1 and check(b):
                        self.weight += 1000

#                index = makeIndex(face, x, y)
#                if state[index] != FINAL_PERM[index]:
#                    continue
#
#                self.weight += 2 if x == 1 or y == 1 else 1

#        for index, color in enumerate(state):
#            if color == FINAL_PERM[index]:
#                self.weight += 1
#
#        for face in range(6):
#            fail = False
#            for x, y in range_2(3, 3):
#                if x != 1 and y != 1:
#                    continue
#
#                index = makeIndex(face, x, y)
#                if state[index] != FINAL_PERM[index]:
#                    fail = True
#                    break
#
#            if not fail:
#                #self.weight += 1000
#                pass

    def check(self):
        for face in range(FACES_COUNT):
            cubeFace = CUBE.faces[face]
            for x, y in range_2(2, 2):
                index = makeIndex(face, x * 2, y * 2)
                c0 = self.state[index]

                if x == 0:
                    c1 = cubeFace.neighbours[DIR_LEFT].getSide(cubeFace)[0]
                else:
                    c1 = cubeFace.neighbours[DIR_RIGHT].getSide(cubeFace)[2]

                if y == 0:
                    c2 = cubeFace.neighbours[DIR_UP].getSide(cubeFace)[2]
                else:
                    c2 = cubeFace.neighbours[DIR_DOWN].getSide(cubeFace)[0]

                if c0 == c1 or c0 == c2 or c1 == c2:
                    self.print()
                    print(face, x * 2, y * 2)
                    
                assert c0 != c1 and c0 != c2 and c1 != c2

    def printFace(self, face):
        for y in range(3):
            for x in range(3):
                print('%s' % COLORS[self.state[makeIndex(face, x, y)]], end = '')
            print("")

    def print(self):
        # print up face
        print('     ---')
        for y in range(3):
            print('    |', end = '')
            for x in range(3):
                print(COLORS[self.state[makeIndex(FACE_UP, x, y)]], end = '')
            print('|')

        # print left, front, right, back faces
        print(' --- --- --- ---')
        for y in range(3):
            print('|', end = '')
            for face in (FACE_LEFT, FACE_FRONT, FACE_RIGHT, FACE_BACK):
                for x in range(3):
                    print(COLORS[self.state[makeIndex(face, x, y)]], end = '')
                print('|', end = '')
            print('')

        # print down face
        print(' --- --- --- ---')
        for y in range(3):
            print('    |', end = '')
            for x in range(3):
                print(COLORS[self.state[makeIndex(FACE_DOWN, x, y)]], end = '')
            print('|')
        print('     ---')

    def applyRotation(self, rotation, back = None):
        newColors = [None for _ in range(len(self.state))]
        for src, dst in enumerate(rotation):
            newColors[dst] = self.state[src]

        for p in newColors:
            assert p is not None

        return RubikState(tuple(newColors), back)

    def __lt__(self, p):
        if self.weight != p.weight:
            return self.weight > p.weight

        return self.state < p.state

    def __eq__(self, p):
        return self.state == p.state

    def __hash__(self):
        if self.state:
            return self.state.__hash__()
        return 0

    @staticmethod
    def read(filename):
        f = open(filename, 'r')

        state = []

        colors = [0 for _ in range(6)]

        face, y = 0, 0
        while face < FACES_COUNT:
            line = f.readline().strip()
            if len(line) == 0:
                continue

            for x in range(3):
                c = COLORS.index(line[x])
                state.append(c)
                colors[c] += 1
                
            y += 1
            if y >= 3:
                face += 1
                y = 0

        f.close()

        assert len(state) == 3 * 3 * 6

        for p in colors:
            assert p == 9
            
        return RubikState(tuple(state), None)

def search(startState):
    MAX_DEPTH = 5

    globVisited = { startState.state }

    startState.check()

    cur     = startState
    best    = startState
    counter = 0
    while cur.state != FINAL_PERM:
        counter += 1

        curBestWeight = -1
        curBest = None

        if cur.weight > best.weight:
            best = cur
            
            match = 0
            for index, color in enumerate(cur.state):
                if color == FINAL_PERM[index]:
                    match += 1

            print("#%d %d w:%d v:%d" % (counter, match, cur.weight, len(globVisited)))
            best.print()

        visited = { cur.state }

        #q = deque([(cur, 0)])
        heap = [cur]
        while len(heap) > 0:
            #state, depth = q.popleft()
            state = heapq.heappop(heap)

            if state.weight > cur.weight and state.state not in globVisited:
                curBest = state
                break

            #if depth >= MAX_DEPTH:# and curBestWeight > cur.weight:
            #    continue

            for index, rot in enumerate(ROTATIONS):
                next = state.applyRotation(rot, (state, index))
                if next.state in visited or next.state in globVisited:
                    continue

                next.check()
                    
                #q.append((next, depth + 1))
                heapq.heappush(heap, next)
                visited.add(next.state)

        cur = curBest
        globVisited.add(cur.state)

    cur.print()
    print("DONE.")

def search_brute(startState):
    visited = set(startState.state)

    heap = [startState]
    #q = deque([startState])

    bestWeight = 0
    bestState  = None

    counter = 0
    while len(heap) > 0:
    #while len(q) > 0:
        cur = heapq.heappop(heap)
        #cur = q.popleft()
        counter += 1

        if cur.weight > bestWeight:
            bestWeight = cur.weight
            bestState  = cur

            match = 0
            for index, color in enumerate(cur.state):
                if color == FINAL_PERM[index]:
                    match += 1

            print("#%03d %d w:%d h:%d v:%d" % (counter // 1000, match, cur.weight, len(heap), len(visited)))
            #print("#%03d %d %d %d" % (counter // 1000, cur.weight, len(q), len(visited)))
            bestState.print()

            #q = deque([cur])

            visited = set(cur.state)

            # TODO: this is faster but can lose solution
            #for p in heap:
            #    visited.remove(p.state)

            heap = [cur]
            continue

        #print("--- step %d" % counter)
        #cur.print()

        if cur.state == FINAL_PERM:
            print("Found: %d steps" % counter)
            print("Visited: %d" % len(visited))
            break

        for index, rot in enumerate(ROTATIONS):
            next = cur.applyRotation(rot, (cur, index))
            if next.state in visited:
                continue

            heapq.heappush(heap, next)
            #q.append(next)
            visited.add(next.state)

state = RubikState.read("input.txt")

search(state)
